package algorithm.tx;

/**
 * <p>
 * 5kg的袋子
 * 物品：
 * 钱：6  10  12
 * Kg：1  2   4
 * <p>
 * 我们把5kg的袋子，拆分成1kg，1kg这样子计算，里面的表格就表示当前重量下能装的最多的钱。表格的数列就表示是要装的物品
 * </p>
 *
 * @author liyi
 * @since 2024/4/18 11:28
 */
public class MoneyBagDp {
    public static void main(String[] args) {

        int value[] = {6, 10, 12};
        int weigth[] = {1, 2, 4};    //购物车那个问题 只需要一个价值就行了，重量都都没有。
        int w = 5;
        int n = 3;
        int dp[][] = new int[n + 1][w + 1];        //n表示是物品，w表示重量,初始化全是0

        for (int i = 1; i <= n; i++) {    //每次加的物品
            for (int cw = 1; cw <= w; cw++) {        //分割的背包
                if (weigth[i - 1] <= cw) {        //表示这个物品可以装进去 weigth[i - 1]表示当前物品重量
                    dp[i][cw] = Math.max(
                            value[i - 1] + dp[i - 1][cw - weigth[i - 1]],
                            dp[i - 1][cw]
                    );
                } else {
                    dp[i][cw] = dp[i - 1][cw];    //不能装
                }
            }
        }
        System.out.println(dp[n][w]);

        // 使用嵌套循环遍历二维数组
        for (int i = 0; i < dp.length; i++) {
            for (int j = 0; j < dp[i].length; j++) {
                System.out.print(dp[i][j] + "\t");
            }
            System.out.println(); // 打印换行
        }
    }
}
/*
0	0	0	0	0	0
0	6	6	6	6	6
0	6	10	16	16	16
0	6	10	16	16	18

 */
